package label.propagation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import graphic.Graph;

/**
 * @author ZhangyiA
 * @describe: traditional label propagation method LPA
 *
 * (1) Initialize the unique label for each node in the network. For a given node x, Cx(0) = x.
 * (2) Set iteration number t = 1.
 * (3) Arrange the nodes of the network in random order, and generate an ordered sequence X = {x1, x2, ···, xn}.
 *
 * (4) For each node x ∈ X, iteratively update the node label according to the formula (1) or (2). In the iterative process, each
 * node changes its label to the one carried by the largest number of its adjacent nodes. As the number of multiple labels reaches
 * maximum, LPA randomly selects one of them to update the node label. (synchronous updating)
 *
 * (5) If iteration number t = maxIter or the label of each node is the same as that of most of its neighboring nodes, then the nodes
 * with the same label are placed in the same community, and the algorithm ends; otherwise, set t = t + 1 and go to step (3).
 *
 * @date 2021/07/16
 */

public class LPA implements Propagation{

    private Graph graph = null;
    private List<Integer> list = new ArrayList<>();

    public LPA(Graph graph){
        this.graph = graph;
        for(int i = 0 ; i < graph.getNode_num() ; i ++){
            list.add(i);
        }
    }

    // 传播结束的标志： 1. tao = maxIter  2. tao < maxItar 但是迭代一轮下来没有任何一个顶点的标签被修改，说明已经稳定，无需再继续迭代了
    public boolean labelPropagation(){
        Collections.shuffle(list); // 每次迭代都需要重新乱序一下
        boolean flag = false; // 是否提前结束的标志
        for(int id : list){
            Map<Integer , ArrayList<Integer>> countLabel = new HashMap<>();
            for(int i = graph.head[id] ; i != -1 ; i = graph.edges[i].getNext()){
                int label = graph.vertices[graph.edges[i].getVertexTo()].pre_com_label; // 获得邻居的标签
                ArrayList<Integer> list = countLabel.containsKey(label) ? countLabel.get(label) : new ArrayList<>();
                list.add(graph.edges[i].getVertexTo());
                countLabel.put(label , list);
            }

            if(countLabel.size() == 0) continue;
            // 修改标签,
            int replaceLabel = getReplaceLabel(countLabel);
            if(replaceLabel != graph.vertices[id].pre_com_label){
                graph.vertices[id].pre_com_label = replaceLabel; // 当前标签需要被修改
                flag = true;
            }
        }
        return flag;
    }

    @SuppressWarnings("Duplicates")
    // 获得邻居出现标签次数最大的标签，如果多个标签出现次数最大，随机选取一个
    public int getReplaceLabel(Map<Integer , ArrayList<Integer>> countLabel){
        int replaceLabel = 0;
        Map<Integer , ArrayList<Integer>> count = new HashMap<>(); // 统计每个标签出现的次数 ，检验最大标签出现的次数 ; 并保存了标签
        int maxSize = -1;
        for(Map.Entry<Integer , ArrayList<Integer>> entry : countLabel.entrySet()){
            int size = entry.getValue().size();
            maxSize = Math.max(size , maxSize);  // 记录标签出现最大的次数
            ArrayList<Integer> list = count.containsKey(size) ? count.get(size) : new ArrayList<>();
            list.add(entry.getKey());
            count.put(size , list);
        }
        if(count.get(maxSize).size() == 1){
            replaceLabel = count.get(maxSize).get(0);
        } else {
            int index = (int)(Math.random() * count.get(maxSize).size()); // 随机生成 index , 随机去一个最大标签
            replaceLabel = count.get(maxSize).get(index);
        }
        return replaceLabel;
    }

    @SuppressWarnings("Duplicates")
    // return community partition result , Map represent community label and each community includes social node
    public Map<Integer , ArrayList<Integer>> getLPACommunityPartitionResult(){
        Map<Integer , ArrayList<Integer>> community = new HashMap<>();
        int iter = 1;
        long starTime1 = System.currentTimeMillis();
        while(iter <= tao && labelPropagation()){
            System.out.println("the iter = " + iter + " have finished !");
            iter ++;
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("cost time = " + (endTime1 - starTime1) + " ms");
        // 获得划分后的结果
        for(int i = 0 ; i < graph.getNode_num() ; i ++){
            int label = graph.vertices[i].pre_com_label;
            ArrayList<Integer> list = community.containsKey(label) ? community.get(label) : new ArrayList<>();
            list.add(i);
            community.put(label , list);
        }
        return community;
    }
}
